package code.oldCode.feishuSpecializedTraining.binary_tree;

import utils.TreeNode;

import java.util.Stack;

public class MyBinaryTree8 {
    // 450. 删除二叉搜索树中的节点
    public TreeNode deleteNode(TreeNode root, int key) {
        // 递归写法
        if (root == null)
            return null;
        if (root.val == key) {
            if (root.left == null)
                return root.right;
            if (root.right == null)
                return root.left;
           TreeNode rightMin = root.right;
           TreeNode rightMinPrev = root; // 可以用注释的递归写法避免prev的存在，但感觉没必要
           while (rightMin.left != null) {
               rightMinPrev = rightMin;
               rightMin = rightMin.left;
           }
           //root.right = deleteNode(root.right, rightMin.val);
           if (rightMinPrev != root) {
               rightMinPrev.left = rightMin.right;
               rightMin.right = root.right;
           }
           rightMin.left = root.left;
           //rightMin.right = root.right;
           return rightMin;
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        } else {
            root.left = deleteNode(root.left, key);
            return root;
        }
    }

    public TreeNode deleteNode_(TreeNode root, int key) {
        // 找到删除节点，非递归写法，折磨
        TreeNode node = root;
        TreeNode prev = null;
        while (node != null) {
            if (node.val == key)
                break;
            else if (node.val < key) {
                prev = node;
                node = node.right;

            } else {
                prev = node;
                node = node.left;

            }
        }
        // 没找到，返回
        if (node == null) return root;
        // 删除节点，把右节点挂在原先位置，右节点的左子树挂在左子树最右面
        // 1. 删除非根节点：使用prev，node左子为空，则换右子即可，右子为空，则换左子即可，都不为空，取右子树最大的一个节点换过来
        if (node != root) {
            if (node.left == null) {
                if (prev.left == node)
                    prev.left = node.right;
                else
                    prev.right = node.right;
            } else if (node.right == null) {
                if (prev.left == node)
                    prev.left = node.left;
                else
                    prev.right = node.left;
            } else {
                // 找右树最小节点
                TreeNode rightMinNode = node.right;
                TreeNode rightMinNodePrev = node;
                while (rightMinNode.left != null) { // 找到右子树的最左节点
                    rightMinNodePrev = rightMinNode;
                    rightMinNode = rightMinNode.left;
                }
                if (rightMinNodePrev != node) { // 如果找到的不是右子树本身的root，则处理
                    rightMinNodePrev.left = rightMinNode.right; // 他的前一个节点不接他了，接他的右子
                    rightMinNode.right = node.right; // 他的右子换为node的右子
                }
                rightMinNode.left = node.left; // 他的左子换为node的左子
                if (prev.left == node)
                    prev.left = rightMinNode;
                else
                    prev.right = rightMinNode;
            }
        }
        // 2. 删除根节点： 左子为空，root改为右子，右子为空改为左子，都不为空，同样找到最右面的最大值作为root
        else {
            if (node.left == null)
                root = node.right;
            else if (node.right == null)
                root = node.left;
            else {
                // 找右数最大节点
                TreeNode rightMinNode = node.right;
                TreeNode rightMinNodePrev = node;
                while (rightMinNode.left != null) {
                    rightMinNodePrev = rightMinNode;
                    rightMinNode = rightMinNode.left;
                }
                if (rightMinNodePrev != node) {
                    rightMinNodePrev.left = rightMinNode.right;
                    rightMinNode.right = node.right;
                }
                rightMinNode.left = node.left;
                root = rightMinNode;
            }
        }

       return root;
    }

    // 669. 修剪二叉搜索树
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null)
            return null;
        if (root.val < low)
            return trimBST(root.right, low, high);
        if (root.val > high)
            return trimBST(root.left, low, high);
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }

    // 108. 将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        return getBSTTree(nums, 0, nums.length - 1);
    }

    public TreeNode getBSTTree(int[] nums, int left, int right) {
        if (left > right)
            return null;
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = getBSTTree(nums, left, mid - 1);
        node.right = getBSTTree(nums, mid + 1, right);
        return node;
    }

    // 538. 把二叉搜索树转换为累加树
    public TreeNode convertBST(TreeNode root) {
        int count = 0;
        TreeNode node = root;
        // 在搜索树中尝试 右-中-左 的反向中序遍历
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.right;
            }
            node = stack.pop();

            count += node.val;
            node.val = count;

            node = node.left;
        }
        return root;
    }

    public static void main(String[] args) {
        int[] array = {2, 0, 33, -1, 1, 25, 40, -1, -1, 11, 31, 34, 45, 10, 18, 29, 32, -1, 36, 43, 46, 4, -1, 12, 24,
                26, 30, -1, -1, 35, 39, 42, 44, -1, 48, 3, 9, -1, 14, 22, -1, -1, 27, -1, -1, -1, -1, 38, -1, 41, -1,
                -1, -1, 47, 49, -1, -1, 5, -1, 13, 15, 21, 23, -1, 28, 37, -1, -1, -1, -1, -1, -1, -1, -1, 8, -1, -1,
                -1, 17, 19, -1, -1, -1, -1, -1, -1, -1, 7, -1, 16, -1, -1, 20, 6};
        TreeNode root = TreeNode.fromArray(array);
        MyBinaryTree8 m = new MyBinaryTree8();
        TreeNode.printTree(root);
        TreeNode.printTree(m.deleteNode_(root, 33));
    }
}
